package com.cat.graphTheory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/course-schedule-ii/description/
 * @create 2025/9/19 19:04
 * @since JDK17
 */

public class Solution12 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer>[] g = new List[numCourses];
        Arrays.setAll(g, i -> new ArrayList<>());
        int[] in = new int[numCourses], q = new int[numCourses];
        int cnt = 0, n = prerequisites.length, l = 0, r = 0;
        for (int i = 0; i < n; i++) {
            int from = prerequisites[i][0], to = prerequisites[i][1];
            g[from].add(to);
            in[to]++;
        }
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0) {
                q[r++] = i;
            }
        }

        while (l < r) {
            int cur = q[l++];
            cnt++;
            for (int x : g[cur]) {
                if (--in[x] == 0) {
                    q[r++] = x;
                }
            }
        }

        return cnt == numCourses ? q : null;
    }
}
